package com.ruoyi.system.spi;

import java.util.ArrayDeque;
import java.util.HashMap;
import java.util.Scanner;

public class Client0422 {

    //给你一棵二叉树的根节点 root ，返回树的最大宽度。
//树的最大宽度是所有层中最大的宽度。
//每一层的宽度被定义为该层最左和最右的非空节点（即，两个端点）之间的长度。将这个
//二叉树视作与满二叉树结构相同，两端点间会出现一些延伸到这一层的 null 节点，这些
//null 节点也计入长度。
//题目数据保证答案将会在32 位带符号整数范围内。
    // 第三题
    public int maxWide(TreeNode root) {


        if (root == null) {
            return 0;
        }
        // 利用广度优先的方式
        ArrayDeque<TreeNodeMap> deque = new ArrayDeque<>();
        deque.offer(new TreeNodeMap(root, 1));
        int max = 1;
        if (!deque.isEmpty()) {
            int wide = deque.size();
            if (wide > 1) {
                TreeNodeMap last = deque.getLast();
                TreeNodeMap first = deque.getFirst();
                max = Math.max(last.index - first.index + 1, max);
            }
            for (int i = 0; i < wide; i++) {
                TreeNodeMap pop = deque.pop();
                deque.add(new TreeNodeMap(pop.treeNode.left, pop.index * 2));
                deque.add(new TreeNodeMap(pop.treeNode.right, pop.index * 2 + 1));
            }
        }

        return max;
    }

    class TreeNode {
        TreeNode left;
        TreeNode right;

    }

    class TreeNodeMap {

        TreeNode treeNode;
        int index;

        public TreeNodeMap(TreeNode treeNode, int index) {
            this.treeNode = treeNode;
            this.index = index;
        }
    }


    //设计一个数据结构，实现LRU Cache的功能(Least Recently Used – 最近最少使用缓存)。它
//支持如下2个操作： get 和 put 。
//int get(int key) – 如果key已存在，则返回key对应的值value（始终大于0）；如果
//key不存在，则返回-1。
//void put(int key, int value) – 如果 key 不存在，将 value 插入；如果 key 已存在，则
//使用 value 替换原先已经存在的值。
//如果容量达到了限制，LRU Cache需要在插入新元素之前，将最近最少使用的元素删
//除。
//请特别注意“使用”的定义：新插入或获取 key 视为被使用一次；而将已经存在的值替换更
//新，不算被使用。
//限制：请在 O(1) 的时间复杂度内完成上述2个操作。

    static class Node {


        int capacity;

        int maxrank = 0;
        int lastrank = 0;
        int curCapacity = 0;
        HashMap<Integer, Integer> valuemap = new HashMap<>();
        HashMap<Integer, Integer> rankkeymap = new HashMap<>();


        HashMap<Integer, Integer> keyrankmap = new HashMap<>();

        public Node(int capacity) {

            this.capacity = capacity;

        }

        // 如果存在，则获取，并更新为最近操作；否则返回-1
        public int get(int key) {

            if (valuemap.keySet().contains(key)) {
                Integer rank = keyrankmap.remove(key);
                // 更新key 与rank 的关系
                keyrankmap.put(key, ++maxrank);
                rankkeymap.remove(rank);
                rankkeymap.put(maxrank, key);
                return valuemap.get(key);
            }

            return -1;
        }

        public void put(int key, int value) {

            if (valuemap.keySet().contains(key)) {
                valuemap.put(key, value);
                //更新对应key的使用情况
                // 需要根据key,获取排名


            } else {
                // 不包含,判断是否超容量
                if (curCapacity + 1 > capacity) {
                    // 超过容量了，删除最新的值
                    // 先删，后加
                    while (rankkeymap.get(lastrank) == null) {
                        lastrank++;
                    }
                    Integer lastkey = rankkeymap.remove(lastrank++);
                    keyrankmap.remove(lastkey);
                    valuemap.remove(lastkey);
                    rankkeymap.put(++maxrank, key);
                    valuemap.put(key, value);
                } else {
                    valuemap.put(key, value);

                    rankkeymap.put(++maxrank, key);
                    keyrankmap.put(key, maxrank);

                    ++curCapacity;
                }

            }

        }

    }


    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = 0;
        if (scanner.hasNext()) {
            n = scanner.nextInt();
        }
        Node node = new Node(n);
        scanner.nextLine();
        while (scanner.hasNextLine()) {

            String s = scanner.nextLine();

            if (s.charAt(0) == 'p') {
                node.put(Integer.valueOf(String.valueOf(s.charAt(1))), Integer.valueOf(String.valueOf(s.charAt(2))));
            }
            if (s.charAt(0) == 'g') {
                int i = node.get(Integer.valueOf(String.valueOf(s.charAt(1))));
                System.out.println(i);
            }

        }

    }
}
